On bipartite graphs of diameter 3 and defect 2
Identifieur interne : 007E14 ( Main/Exploration ); précédent : 007E13; suivant : 007E15On bipartite graphs of diameter 3 and defect 2
Auteurs : Charles Delorme [France] ; Leif K. J Rgensen [Danemark] ; Mirka Miller [Australie, République tchèque] ; Guillermo Pineda-Villavicencio [Australie, Cuba]Source :
- Journal of Graph Theory [ 0364-9024 ] ; 2009-08.
English descriptors
- KwdEn :
- Adjacency matrix, Adjacent vertices, Antidirected, Bipartite, Bipartite graph, Bipartite graphs, Bipartite moore, Bipartite moore graphs, Computer science, Defect, Defect matrix, Digraph, Diophantine equation, Graph theory, Matrix, Maximum degree, Other vertex, Partite, Partite sets, Perfect square, Perfect squares, Prime power, Projective plane, Quadratic forms, Regular digraphs, Same group, Symmetric group, Symmetric matrices, Unique bipartite.
- Teeft :
- Adjacency matrix, Adjacent vertices, Antidirected, Bipartite, Bipartite graph, Bipartite graphs, Bipartite moore, Bipartite moore graphs, Computer science, Defect, Defect matrix, Digraph, Diophantine equation, Graph theory, Matrix, Maximum degree, Other vertex, Partite, Partite sets, Perfect square, Perfect squares, Prime power, Projective plane, Quadratic forms, Regular digraphs, Same group, Symmetric group, Symmetric matrices, Unique bipartite.
Abstract
We consider bipartite graphs of degree Δ≥2, diameter D=3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (Δ, 3, −2) ‐graphs. We prove the uniqueness of the known bipartite (3, 3, −2) ‐graph and bipartite (4, 3, −2)‐graph. We also prove several necessary conditions for the existence of bipartite (Δ, 3, −2) ‐graphs. The most general of these conditions is that either Δ or Δ−2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when Δ=6 and Δ=9, we prove the non‐existence of the corresponding bipartite (Δ, 3, −2)‐graphs, thus establishing that there are no bipartite (Δ, 3, −2)‐graphs, for 5≤Δ≤10. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 271–288, 2009
Url:
DOI: 10.1002/jgt.20378
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000413
- to stream Istex, to step Curation: 000413
- to stream Istex, to step Checkpoint: 000E51
- to stream Main, to step Merge: 008509
- to stream Main, to step Curation: 007E14
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On bipartite graphs of diameter 3 and defect 2</title><author><name sortKey="Delorme, Charles" sort="Delorme, Charles" uniqKey="Delorme C" first="Charles" last="Delorme">Charles Delorme</name></author><author><name sortKey="J Rgensen, Leif K" sort="J Rgensen, Leif K" uniqKey="J Rgensen L" first="Leif K." last="J Rgensen">Leif K. J Rgensen</name></author><author><name sortKey="Miller, Mirka" sort="Miller, Mirka" uniqKey="Miller M" first="Mirka" last="Miller">Mirka Miller</name></author><author><name sortKey="Pineda Illavicencio, Guillermo" sort="Pineda Illavicencio, Guillermo" uniqKey="Pineda Illavicencio G" first="Guillermo" last="Pineda-Villavicencio">Guillermo Pineda-Villavicencio</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:158E7B5DCAB91FC20D57691319DAFC48291FC610</idno><date when="2009" year="2009">2009</date><idno type="doi">10.1002/jgt.20378</idno><idno type="url">https://api.istex.fr/document/158E7B5DCAB91FC20D57691319DAFC48291FC610/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000413</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000413</idno><idno type="wicri:Area/Istex/Curation">000413</idno><idno type="wicri:Area/Istex/Checkpoint">000E51</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000E51</idno><idno type="wicri:doubleKey">0364-9024:2009:Delorme C:on:bipartite:graphs</idno><idno type="wicri:Area/Main/Merge">008509</idno><idno type="wicri:Area/Main/Curation">007E14</idno><idno type="wicri:Area/Main/Exploration">007E14</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On bipartite graphs of diameter 3 and defect 2</title><author><name sortKey="Delorme, Charles" sort="Delorme, Charles" uniqKey="Delorme C" first="Charles" last="Delorme">Charles Delorme</name><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation><affiliation wicri:level="1"><country xml:lang="fr">France</country><wicri:regionArea>Lab. de Recherche en Informatique, University de Paris‐Sud, 91405 Orsay</wicri:regionArea><wicri:noRegion>91405 Orsay</wicri:noRegion><wicri:noRegion>91405 Orsay</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="J Rgensen, Leif K" sort="J Rgensen, Leif K" uniqKey="J Rgensen L" first="Leif K." last="J Rgensen">Leif K. J Rgensen</name><affiliation wicri:level="1"><country wicri:rule="url">Danemark</country></affiliation><affiliation wicri:level="4"><country xml:lang="fr">Danemark</country><wicri:regionArea>Department of Mathematics and Computer Science, Aalborg University, F. Bajers Vej 7, DK‐9220 Aalborg Ø</wicri:regionArea><orgName type="university">Université d'Aalborg</orgName><placeName><settlement type="city">Aalborg</settlement><region nuts="2" type="region">Jutland du Nord</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Danemark</country></affiliation></author><author><name sortKey="Miller, Mirka" sort="Miller, Mirka" uniqKey="Miller M" first="Mirka" last="Miller">Mirka Miller</name><affiliation wicri:level="1"><country wicri:rule="url">Australie</country></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Australie</country><wicri:regionArea>School of Electrical Engineering and Computer Science, The University of Newcastle, Australia, Newcastle</wicri:regionArea><wicri:noRegion>Newcastle</wicri:noRegion></affiliation><affiliation wicri:level="1"><country xml:lang="fr">République tchèque</country><wicri:regionArea>Department of Mathematics, University of West Bohemia, Pilsen</wicri:regionArea><wicri:noRegion>Pilsen</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Australie</country></affiliation></author><author><name sortKey="Pineda Illavicencio, Guillermo" sort="Pineda Illavicencio, Guillermo" uniqKey="Pineda Illavicencio G" first="Guillermo" last="Pineda-Villavicencio">Guillermo Pineda-Villavicencio</name><affiliation></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Australie</country><wicri:regionArea>School of Information Technology and Mathematical Sciences, University of Ballarat, Ballarat</wicri:regionArea><wicri:noRegion>Ballarat</wicri:noRegion></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Cuba</country><wicri:regionArea>Department of Computer Science, University of Oriente, Santiago de Cuba</wicri:regionArea><wicri:noRegion>Santiago de Cuba</wicri:noRegion></affiliation><affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j" type="main">Journal of Graph Theory</title><title level="j" type="alt">JOURNAL OF GRAPH THEORY</title><idno type="ISSN">0364-9024</idno><idno type="eISSN">1097-0118</idno><imprint><biblScope unit="vol">61</biblScope><biblScope unit="issue">4</biblScope><biblScope unit="page" from="271">271</biblScope><biblScope unit="page" to="288">288</biblScope><biblScope unit="page-count">18</biblScope><publisher>Wiley Subscription Services, Inc., A Wiley Company</publisher><pubPlace>Hoboken</pubPlace><date type="published" when="2009-08">2009-08</date></imprint><idno type="ISSN">0364-9024</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0364-9024</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Adjacency matrix</term><term>Adjacent vertices</term><term>Antidirected</term><term>Bipartite</term><term>Bipartite graph</term><term>Bipartite graphs</term><term>Bipartite moore</term><term>Bipartite moore graphs</term><term>Computer science</term><term>Defect</term><term>Defect matrix</term><term>Digraph</term><term>Diophantine equation</term><term>Graph theory</term><term>Matrix</term><term>Maximum degree</term><term>Other vertex</term><term>Partite</term><term>Partite sets</term><term>Perfect square</term><term>Perfect squares</term><term>Prime power</term><term>Projective plane</term><term>Quadratic forms</term><term>Regular digraphs</term><term>Same group</term><term>Symmetric group</term><term>Symmetric matrices</term><term>Unique bipartite</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Adjacency matrix</term><term>Adjacent vertices</term><term>Antidirected</term><term>Bipartite</term><term>Bipartite graph</term><term>Bipartite graphs</term><term>Bipartite moore</term><term>Bipartite moore graphs</term><term>Computer science</term><term>Defect</term><term>Defect matrix</term><term>Digraph</term><term>Diophantine equation</term><term>Graph theory</term><term>Matrix</term><term>Maximum degree</term><term>Other vertex</term><term>Partite</term><term>Partite sets</term><term>Perfect square</term><term>Perfect squares</term><term>Prime power</term><term>Projective plane</term><term>Quadratic forms</term><term>Regular digraphs</term><term>Same group</term><term>Symmetric group</term><term>Symmetric matrices</term><term>Unique bipartite</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We consider bipartite graphs of degree Δ≥2, diameter D=3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (Δ, 3, −2) ‐graphs. We prove the uniqueness of the known bipartite (3, 3, −2) ‐graph and bipartite (4, 3, −2)‐graph. We also prove several necessary conditions for the existence of bipartite (Δ, 3, −2) ‐graphs. The most general of these conditions is that either Δ or Δ−2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when Δ=6 and Δ=9, we prove the non‐existence of the corresponding bipartite (Δ, 3, −2)‐graphs, thus establishing that there are no bipartite (Δ, 3, −2)‐graphs, for 5≤Δ≤10. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 271–288, 2009</div></front></TEI><affiliations><list><country><li>Australie</li><li>Cuba</li><li>Danemark</li><li>France</li><li>République tchèque</li></country><region><li>Jutland du Nord</li></region><settlement><li>Aalborg</li></settlement><orgName><li>Université d'Aalborg</li></orgName></list><tree><country name="France"><noRegion><name sortKey="Delorme, Charles" sort="Delorme, Charles" uniqKey="Delorme C" first="Charles" last="Delorme">Charles Delorme</name></noRegion><name sortKey="Delorme, Charles" sort="Delorme, Charles" uniqKey="Delorme C" first="Charles" last="Delorme">Charles Delorme</name><name sortKey="Delorme, Charles" sort="Delorme, Charles" uniqKey="Delorme C" first="Charles" last="Delorme">Charles Delorme</name></country><country name="Danemark"><noRegion><name sortKey="J Rgensen, Leif K" sort="J Rgensen, Leif K" uniqKey="J Rgensen L" first="Leif K." last="J Rgensen">Leif K. J Rgensen</name></noRegion><name sortKey="J Rgensen, Leif K" sort="J Rgensen, Leif K" uniqKey="J Rgensen L" first="Leif K." last="J Rgensen">Leif K. J Rgensen</name><name sortKey="J Rgensen, Leif K" sort="J Rgensen, Leif K" uniqKey="J Rgensen L" first="Leif K." last="J Rgensen">Leif K. J Rgensen</name></country><country name="Australie"><noRegion><name sortKey="Miller, Mirka" sort="Miller, Mirka" uniqKey="Miller M" first="Mirka" last="Miller">Mirka Miller</name></noRegion><name sortKey="Miller, Mirka" sort="Miller, Mirka" uniqKey="Miller M" first="Mirka" last="Miller">Mirka Miller</name><name sortKey="Miller, Mirka" sort="Miller, Mirka" uniqKey="Miller M" first="Mirka" last="Miller">Mirka Miller</name><name sortKey="Pineda Illavicencio, Guillermo" sort="Pineda Illavicencio, Guillermo" uniqKey="Pineda Illavicencio G" first="Guillermo" last="Pineda-Villavicencio">Guillermo Pineda-Villavicencio</name></country><country name="République tchèque"><noRegion><name sortKey="Miller, Mirka" sort="Miller, Mirka" uniqKey="Miller M" first="Mirka" last="Miller">Mirka Miller</name></noRegion></country><country name="Cuba"><noRegion><name sortKey="Pineda Illavicencio, Guillermo" sort="Pineda Illavicencio, Guillermo" uniqKey="Pineda Illavicencio G" first="Guillermo" last="Pineda-Villavicencio">Guillermo Pineda-Villavicencio</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 007E14 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 007E14 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:158E7B5DCAB91FC20D57691319DAFC48291FC610
|texte= On bipartite graphs of diameter 3 and defect 2
}}
| This area was generated with Dilib version V0.6.33. |  |